#include <iostream>
#include <stdio.h>

#include <iostream>
#include <vector>

class Solution {
private:
    // std::vector<std::vector<std::string>> result;
    // std::vector<int> path;
    // n 为棋盘大小  
    //row是当前递归到棋盘的第几行
    bool backtracking (std::vector<std::vector<char>>& board) {
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                if(board[i][j] != '.') continue;
                for(char k = '1'; k <= '9'; k++){
                    if(isValid(i,j,k,board)){
                        board[i][j] = k;
                        if(backtracking(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
            
        }
        return true;
    }

    bool isValid(int row,int col, char val, std::vector<std::vector<char>>& board)
    {
        for (int i = 0; i < 9; i++) { // 判断行里是否重复
            if (board[row][i] == val) {
                return false;
            }
        }
        for (int j = 0; j < 9; j++) { // 判断列里是否重复
            if (board[j][col] == val) {
                return false;
            }
        }
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == val ) {
                    return false;
                }
            }
        }
        return true;
    }

public:
    bool solveSuduku(std::vector<std::vector<char>>& board) {
        // result.clear();
        // std::vector<std::string> chessboard(n,std::string(n, 'N'));
        
        return backtracking(board);;
    }
};

int main(int argv, char**argc)
{

    printf("************  test hello zc!!!   **************\n");
    /* add test code! */
    Solution solve;
    std::vector<std::vector<char>> ret = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };

    if(!solve.solveSuduku(ret))
        return -1;
    // printf("[ ");
    for(auto p:ret){
        // printf("[");
        for(auto q:p){
            printf("%c ", q);
        }
        printf("\n");    
    }
    // printf("%d\n", ret.size());
    return 0;
}
